﻿// Road Construction Aizu - 2249.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define  _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>



using namespace std;
//Road Construction Aizu - 2249 
//https://vjudge.csgrandeur.cn/problem/Aizu-2249

/*
问题 H：
国王默瑟是 ACM 王国的国王。他的王国有一个首都和一些城市。
令人惊奇的是，王国里现在还没有公路。最近，他计划在首都和城市之间修建道路，
但结果表明，计划的建筑成本比预期的要高得多。
为了降低成本，他决定制定一个新的建设计划，从原计划中删除一些道路。
不过，他认为新计划应满足以下条件：
对于每一对城市，都有一条路线（一组道路）连接它们。
首都与每个城市之间的最小距离与原计划相比没有变化。
可能有很多计划都能满足上述条件，但国王默瑟想要知道成本最低的计划。
你的任务是编写一个程序，读取他的原始计划，并计算出成本最小的新计划的成本。
输入
输入由几个数据集组成。每个数据集的格式如下。
N M
u1 v1 d1 c1
.
.
.
uM vM dM cM
每个数据集的第一行以两个整数 N 和 M 开头（1 ≤ N ≤ 10000，0 ≤ M ≤ 20000）。
N 和 M 分别表示原始规划中的城市数量和道路数量。
下面的 M 行描述了原始规划中的道路信息。
第 i 行包含四个整数：ui、vi、di 和 ci（1≤ui，vi≤N，ui≠vi，1≤di≤1000，1≤ci≤1000）。
ui、vi、di 和 ci 表示有一条道路连接第 ui- 个城市和第 vi- 个城市，其长度为 di，建设成本为 ci。
每条道路都是双向的。没有两条道路连接同一对城市。第 1 个城市是王国的首都。
输入结束的标志是一行包含两个 0 的空格。您不应将该行作为数据集处理。
输出
对于每个数据集，打印满足一行条件的计划的最小成本。
输入示例
3 3
1 2 1 2
2 3 2 1
3 1 3 2
5 5
1 2 2 2
2 3 1 1
1 4 1 1
4 5 1 1
5 3 1 1
5 10
1 2 32 10
1 3 43 43
1 4 12 52
1 5 84 23
2 3 58 42
2 4 86 99
2 5 57 83
3 4 11 32
3 5 75 21
4 5 23 43
5 10
1 2 1 53
1 3 1 65
1 4 1 24
1 5 1 76
2 3 1 19
2 4 1 46
2 5 1 25
3 4 1 13
3 5 1 65
4 5 1 34
0 0
样本输入的输出
3
5
137
218
*/

//代码未通过
int main() {
	return 0;
}


//const int N = 10010;
//const int M = 20010;
//
//int n, m;
//int h[N], W[M * 2], e[M*2],C[M * 2], ne[M*2], idx;
//int dist[N];
//bool st[N];
//
//
//void add(int a, int b, int w, int c) {
//	e[idx] = b, W[idx] = w, C[idx] = c, ne[idx] = h[a], h[a] = idx++;
//}
//
//int dijkstra() {
//	//memset(dist, 0x3f, sizeof dist);
//	for (int i = 0; i < N; i++) {
//		dist[i] = 299999999;
//	}
//	memset(st, 0, sizeof st);
//	dist[1] = 0; 
//
//	priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> heap;
//	heap.push({ 0, 0,1 });      // first存储距离，second存储开销  third存储点id
//	int ans = 0;
//	while (heap.size())
//	{
//		auto t = heap.top();
//		heap.pop();
//
//		int distance = t[0], currcost = t[1],ver = t[2];
//
//		if (st[ver]) continue;
//		st[ver] = true;
//		ans += currcost;
//		for (int i = h[ver]; i != -1; i = ne[i])
//		{
//			int j = e[i]; 
//			if ( (dist[j] >= distance + W[i] ) )
//			{
//				dist[j] = distance + W[i];
//				heap.push({ dist[j], C[i], j });
//			}
//		}
//	}
//
//	return ans;
//}
//
//#define ONLINE_JUDGE
//
//int main()
//{
//#ifndef ONLINE_JUDGE
//	freopen("in1 (4).txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//#endif
//
//	while (cin >> n >> m) {
//		if (n == 0 || m == 0) break;
//		memset(h, -1, sizeof h); idx = 0;
//		for (int i = 0; i < m; i++) {
//			int a, b, w, c;
//			cin >> a >> b >> w >> c;
//			add(a, b, w, c); add(b, a, w, c);
//		}
//
//		cout << dijkstra() << endl;
//	}
//
//#ifndef ONLINE_JUDGE
//	fclose(stdin);
//	fclose(stdout);
//#endif
//	return 0;
//}
//
// 